The technique of using mixed integer linear programming (MILP) for multi-vehicle path planning purposes in an obstacle environment has been recently developed. The technique has been proven useful at least in an experimental context and laboratory systems that implement MILP for path planning have been built as shown in M. G. Earl and R. Dandrea, “Modeling and control of a multi-agent system using mixed integer linear programming”, In Proceedings of the 41st IEEE Conference on Decision and Control, December 2002.
A mixed integer linear programming (MILP) problem is very similar to a linear programming (LP) problem in that there is a set of linear objective functions and constraints, under which an optimal solution may be found. A MILP problem differs from an LP problem only in that some of the variables are restricted to be integers and thus the solution space for a MILP problem is a subset of that of a similar LP problem (the MILP problem without the integer restrictions). A major advantage of using MILP as a problem formulation is that fast, parallelizable, and commercially available MILP solvers such as ILOG CPLEX are readily available.
Mathematical programming modeling languages such as AMPL, have been developed to take advantage of higher level constructs in expressing a complex problem and the ability to be mapped to multiple solvers, much like a high level computer programming language such as C++ is more versatile for many programmers and can be mapped (or compiled) onto assembly languages for multiple platforms.
T. Schouwenaars, B. De Moor, E. Feron, and J. How, “Mixed integer programming for multi-vehicle path planning”, In 2001 European Control Conference, September 2001, describes a basic MILP problem formulation combining fuel-optimal path planning for multiple vehicles with double-integrator vehicle dynamics and obstacles in two-dimensional space.
T. Schouwenaars, E. Feron, and J. How, “Safe receding horizon path planning for autonomous vehicles”, In 40th Annual Allerton Conference on Communication, Control, and Computing, October 2002, guarantees a priori safety for a MILP path planning implementation with fixed obstacles and limited planning horizon length by incorporating safe maneuvers.
J. Bellingham, A. Richards, and J. How, “Receding horizon control of autonomous aerial vehicles”, In 2002 American Control Conference, May 2002, augments a receding-horizon implementation of MILP path planning with a cost-to-go map in order to avoid entrapment behind relatively large obstacles.
T. Schouwenaars, B. Mettler, E. Feron, and J. How, “Hybrid architecture for full envelope autonomous rotorcraft guidance”, In Proceedings of the 59th Forum of the American Helicopter Society, May 2003, allows the use of multiple linear time invariant (LTI) modes and discrete finite time maneuvers in a MILP path planning problem as a first step in providing full flight envelope trajectory planning.
The above references do not address path planning in an environment containing threats. There is a need for a method of generating air vehicle flight trajectories for flying over a terrain and avoiding obstacles and with multiple threats.